#include "leetcode_util.h"

void showVector(vector<int>& A) {
    vector<int>::iterator itr = A.begin();
    for(; itr != A.end();) {
        printf("%d", *itr);
        if (++itr != A.end()) {
            printf(" ");
        } else {
            printf("\n");
        }
    }
}

bool isSameVector1(vector<int>& v1, vector<int>& v2) {
	for (auto i1 : v1) {
		bool isDup = false;
		for (auto i2 : v2) {
			if (i1 == i2) {
				isDup = true;
				break;
			}
		}
		if (!isDup) return false;
	}
	for (auto i2 : v2) {
		bool isDup = false;
		for (auto i1 : v1) {
			if (i1 == i2) {
				isDup = true;
				break;
			}
		}
		if (!isDup) return false;
	}
	return true;
}

bool isSameVector(vector<int> v1, vector<int> v2) {
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
	return v1 == v2;
}

void helper(vector<int>& nums, int cur_idx, int l, int n, int s, vector<int> pre, vector<vector<int>>& res) {
/*    printf("=-= cur_idx: %d, need: %d, sum: %d pre: '", cur_idx, n, s);
    for (auto i : pre) {
        printf("%d,", i);
    }
    printf("'\n");*/
    if (cur_idx == l) {
        return;
    }
    if (n == 1) {
        for (int i = cur_idx; i < l; ++i) {
            if (nums[i] == s) {
                pre.push_back(nums[i]);
                bool isDup = false;
                for (auto _v : res) {
                    if (isSameVector(_v, pre)) {
                        isDup = true;
                        break;
                    }
                }
                if (!isDup) {
                    res.push_back(pre);
                }
                break;
            }
        }
    } else {
        helper(nums, cur_idx+1, l, n, s, pre, res); // no choose nums[i]
        pre.push_back(nums[cur_idx]); // choose nums[i]
        helper(nums, cur_idx+1, l, n-1, s-nums[cur_idx], pre, res);
    }
}

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    helper(nums, 0, nums.size(), 3, 0, {}, result);
    return result;
}

vector<vector<int>> threeSum1(vector<int>& nums) {
    if (nums.empty()) return {};
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    if (nums.back() < 0 || nums.front() > 0) return {};
    showVector(nums);

    int l = nums.size();
    for (int i = 0; i < l - 2; ++i) {
        // for each nums[i], find the fixed target from idx(i+1)
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int target = 0 - nums[i], j = i+1, k = l - 1;
        while (j < k) {
            if (nums[j] + nums[k] == target) {
                res.push_back({nums[i], nums[j], nums[k]});
                // pass the same solution if nums[i] == nums[i+1]
                while (j < k && nums[j] == nums[j+1]) ++j;
                while (j < k && nums[k] == nums[k-1]) --k;
                ++j;
                --k;
            } else if (nums[j] + nums[k] < target) { // increase i so that the sum becomes bigger
                ++j;
            } else {
                --k;
            }
        }
    }
    return res;
}

void test(vector<int>& v) {
    vector<vector<int>> res = threeSum(v);
    printf("Ori: ");
    showVector(v);
    for (auto _v : res) {
        printf("Result: ");
        showVector(_v);
    }
}

int main() {
    //vector<int> v{-1, 0, 1, 2, -1, -4};
    vector<int> v{-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
    //vector<int> v{3,0,-2,-1,1,2};
    test(v);
}

